package algo.reverselinkedlist;

/**
 * Created by mHandler on 2018/5/30 0030.
 * Description:Java实现反转链表
 */
public class ListNode {

    static class Node{
        int val;
        Node next;
        public Node(int val){
            this.val = val;
        }
    }
    public static Node reverseList(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        Node reHead = null;// 定义新链表头结点
        while (head != null) {
            Node cur = head.next;// 记录下一个节点
            head.next = reHead;// 将rehead节点连接到head节点上
            reHead = head;// 让rehead指向head
            head = cur;// 将head指向下一个节点
        }
        return reHead;
    }

    /**
     * 遍历，将当前节点的下一个节点缓存后更改当前节点指针
     */
    public static Node reverse2(Node head) {
        if (head == null)
            return head;
        Node pre = head;// 上一结点
        Node cur = head.next;// 当前结点
        Node tmp;// 临时结点，用于保存当前结点的指针域（即下一结点）
        while (cur != null) {// 当前结点为null，说明位于尾结点
            tmp = cur.next;
            cur.next=(pre);// 反转指针域的指向

            // 指针往下移动
            pre = cur;
            cur = tmp;
        }
        // 最后将原链表的头节点的指针域置为null，还回新链表的头结点，即原链表的尾结点
        head.next=(null);

        return pre;
    }

    /**
     * 递归，在反转当前节点之前先反转后续节点
     */
    public static Node Reverse1(Node head) {
        // head看作是前一结点，head.getNext()是当前结点，reHead是反转后新链表的头结点
        if (head == null || head.next == null) {
            return head;// 若为空链或者当前结点在尾结点，则直接还回
        }
        Node reHead = Reverse1(head.next);// 先反转后续节点head.getNext()
        head.next.next=(head);// 将当前结点的指针域指向前一结点
        head.next=(null);// 前一结点的指针域令为null;
        return reHead;// 反转后新链表的头结点
    }

    public static void main(String[] args) {
        Node a = new ListNode.Node(1);
        Node b = new ListNode.Node(2);
        Node c = new ListNode.Node(3);
        Node d = new ListNode.Node(4);
        Node e = new ListNode.Node(5);
        a.next=b;
        b.next = c;
        c.next = d;
        d.next = e;
    /**
     * 原始链表
     * */
        Node head = a;
        while (head != null){
            System.out.print(head.val+" ");
            head = head.next;
        }
        System.out.println();
        /**
         * 链表反转
         * */
        head = reverse2(a);
        while (head != null){
            System.out.print(head.val+" ");
            head = head.next;
        }
        System.out.println();
    }

}
